class Graph<T = string> {
  private vertices: T[]; // 顶点集合
  private adjList: Map<T, T[]>; // 邻接表
  constructor() {
    this.vertices = [];
    this.adjList = new Map();
  }

  // 添加顶点
  addVertex(value: T) {
    if (!this.vertices.includes(value)) {
      this.vertices.push(value);
      this.adjList.set(value, []);
    } else {
      console.log("顶点已存在");
    }
  }

  // 添加边
  addEdge(from: T, to: T) {
    if (!this.vertices.includes(from) || !this.vertices.includes(to)) {
      console.log("顶点不存在");
      return;
    }
    this.adjList.get(from)?.push(to);
    this.adjList.get(to)?.push(from);
  }

  // 遍历图
  traverse() {
    this.vertices.forEach((vertex) => {
      const edges = this.adjList.get(vertex);
      console.log(`${vertex} -> ${edges?.join(" ")}`);
    });
  }

  // 检查顶点是否存在
  containsVertex(value: T) {
    return this.vertices.includes(value);
  }

  // 检查边是否存在
  containsEdge(from: T, to: T) {
    const edges = this.adjList.get(from);
    return edges?.includes(to) || edges?.includes(from);
  }

  // 获取顶点的度数
  getDegree(vertex: T) {
    const edges = this.adjList.get(vertex);
    return edges?.length || 0;
  }

  // 广度优先搜索
  breadthFirstSearch() {
    if (!this.vertices.length) return;
    const visited: Set<T> = new Set();
    const queue: T[] = []; // 队列,先进先出
    queue.push(this.vertices[0]);
    visited.add(this.vertices[0]);
    while (queue.length) {
      const vertex = queue.shift()!;
      console.log(vertex);

      const neighbors = this.adjList.get(vertex);
      if (!neighbors) continue;
      for (const nei of neighbors) {
        if (!visited.has(nei)) {
          queue.push(nei);
          visited.add(nei);
        }
      }
    }
  }

  // 深度优先搜索
  depthFirstSearch() {
    if (!this.vertices.length) return;
    const visited: Set<T> = new Set();
    visited.add(this.vertices[0]);
    const stack: T[] = []; // 栈结构，先进后出
    stack.push(this.vertices[0]);

    while (stack.length) {
      const vertex = stack.pop()!;
      console.log(vertex);

      const neighbors = this.adjList.get(vertex);
      if (!neighbors) continue;
      for (let i = neighbors.length - 1; i >= 0; i--) {
        const nei = neighbors[i];
        if (!visited.has(nei)) {
          stack.push(nei);
          visited.add(nei);
        }
      }
    }
  }
}

const graph = new Graph<string>();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");
graph.addVertex("G");
graph.addVertex("H");
graph.addVertex("I");

graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("A", "D");
graph.addEdge("C", "D");
graph.addEdge("C", "G");
graph.addEdge("D", "G");
graph.addEdge("D", "H");
graph.addEdge("B", "E");
graph.addEdge("B", "F");
graph.addEdge("E", "I");

graph.traverse();
console.log(graph.getDegree("I"));
console.log("----广度优先----");
graph.breadthFirstSearch();
console.log("----深度优先----");
graph.depthFirstSearch();
console.log();

export {};
